[UVA11362]Phone List

发表于 | 分类于 ， | | 阅读次数:

题目

PDF

题解

虽然我很想说这是一道字典树模板题，但是还是有点技巧的。
对于每组输入，我们先把它存入字典树，然后再来查找（也就是所谓的离线）
为了说明方便，用表格说明一下变量吧

变量名 变量作用
$st$ 保存读入的字符串，用于离线
$word$ 保存字典树每条边被覆盖的次数，遍历时为1说明不是前缀
$ch$ 字典树，第一维是编号，第二维是哪条边，值为指向的点
$sz$ 用来编号，类似于链式前向星里的$tot$

关键是遍历的时候，只要word为1就返回0（就是它自己啊），能顺利的走下来就返回1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX = 1e5 + 10;
int t,n;
char st[10100][10];
int word[MAX],ch[MAX][10],sz;

void reset(){//每组数据需要重置
   sz = 1;
   memset(ch[0],0,sizeof(ch[0]));
   memset(word,0,sizeof(word));
}

void insert(char *s){//插入进字典树
    int nl = strlen(s),u = 0;
    for(int i = 0 ; i < nl ;i++){
        int c = s[i] - '0';
        if(! ch[u][c]){
          memset(ch[sz],0,sizeof(ch[sz]));
            ch[u][c] = sz++;
        }
        u = ch[u][c];
        word[u]++;
    }
}

int find(char *s){//是否是前缀
   int nl = strlen(s),u = 0;
   for(int i = 0; i < nl; i++){
        int c = s[i] - '0';
        u = ch[u][c];
        if(word[u] == 1) return 0;
   }
   return 1;
}

int main(){
    cin>>t;
    while(t--){
        reset();
        scanf("%d",&n);
        for(int i = 1 ; i <= n; i++){
            scanf("%s",st[i]);
            insert(st[i]);
        }
        int ok = 1;
        for(int i = 1 ; i <= n; i++)
            if(find(st[i])){
                ok = 0;
                break;
            }
        if(ok) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}